#!/usr/bin/env python
# -*- coding: UTF-8 -*-
"""
"""

from math import log

def getDigit(n, b, k): return (n // b ** k) % b  # pulls the selected digit

def mkBlanks(k): return [ [] for i in range(k) ]  # create a list of empty lists to hold the split by digit

def split(l, b, k):
    x = mkBlanks(b)
    for i in l: x[getDigit(i, b, k)].append(i)  # append the number to the list selected by the digit
    return x

def merge(x):
    l = []
    for i in x: l.extend(i)  # concatenate the lists back in order for the next step
    return l

def max(l): return reduce(lambda x, y: x if x > y else y, map(abs, l))  # largest abs value element of a list

def radixSort(l, b):
    passes = int(log(max(l), b) + 1)  # there are as many passes as the are digits in the longest number
    t = list(l)
    for i in range(passes): t = merge(split(t, b, i))
    return t

###
if __name__=="__main__":
    l = [1, 2, 3, 6, 4, 5, 9, 8, 7]
    print l
    x = radixSort(l, 10)
    print x
